home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / PASCAL / ALLSWAGS.ZIP / SWAGG-M.ZIP / MISC.SWG / 0145_Lou's Maze Algorithm.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1995-05-26  |  4.9 KB  |  89 lines
  1. {
  2. LOU'S MAZE ALGORITHM
  3.  
  4. We all want to create mazes at some time or other; I devised one effective
  5. maze-generating algorithm.  I will be discussing a rectangular maze, but
  6. it should be possible to use the principles I describe to create mazes of
  7. different shapes.  I will also be discussing mazes with no "islands" in
  8. them or any other features that would make it impossible to walk the
  9. entire maze with one hand against the wall.
  10.  
  11. First of all, you need to create a two-dimensional array to describe the
  12. maze territory.  Each grid element should, at the very least, contain
  13. a boolean to indicate whether or not there is a wall at that spot.  Your
  14. grid should have *ODD* dimensions, so that you can maintain a wall /
  15. corridor / wall / corridor / wall / etc. pattern.  Now flag the outside
  16. edges of the grid as "walls", and the entire interior as non-walls.
  17.  
  18. Next, select an entrance and exit to the maze.  The entrance and exit
  19. will be on the edges of the grid, but with *EVEN* coordinates (so they
  20. will open up into a corridor and not a wall).  Flag the entrance and
  21. exit as non-walls.
  22.  
  23. Now select several spots on the edges of the grid, from which to
  24. start generating the insides of the maze.  All these spots must have
  25. *ODD* coordinates, so that they will not ever grow into corridors.
  26. What we will be doing is growing walls from these "seed points" to
  27. fill the maze.  (Each seed point is a record that should just consist
  28. of an x and y coordinate, indicating a maze location to grow a wall
  29. segment from.)
  30.  
  31. You will need to set up a large array to accommodate a great number of
  32. seeds: every time you add a wall segment, you add seed points.  By my
  33. guesstimates, the maximum number of seeds you're ever going to need is:
  34. (mazeheight - 3)*(mazewidth - 3) / 2.
  35.  
  36. Keep executing this loop until you run out of seeds:
  37.  
  38.   - Randomly select a seed.  Extend the wall in some valid direction
  39.     from this seed point, by turning into walls the grid locations one
  40.     unit and two units away from the seed.  To prevent the maze from
  41.     closing off at any point, DO NOT EXTEND A WALL TO ANY POINT THAT
  42.     IS ALREADY MARKED AS A WALL!  (With this rule, you never close off
  43.     the maze; you simply complicate the path from beginning to end.)
  44.  
  45.   - Remove this seed.  It's done its job.
  46.  
  47.   - Add three seed points at this new location.  (The assumption is
  48.     that the wall could grow in three directions from this new point;
  49.     if you want to be more exacting, you can add as many seeds as there
  50.     are directions that the wall could extend from that point.  It
  51.     really doesn't matter much, except for the possibility of running
  52.     out of seed point array elements if you always add 3.)
  53.  
  54.   - Seed maintenance: go through your list of seeds and eliminate any
  55.     seeds that cannot extend in any valid direction.
  56.  
  57. Once you are out of seeds, the maze is complete.  You are done.
  58. ------------------------------------------------------------------------
  59.  
  60. As for traversing a maze: you are likely aware of the "right-hand rule"
  61. for walking a maze, by starting at the entrance, keeping your right hand
  62. on the wall at all times, and following your nose.  Sooner or later, you
  63. will get to the exit.  I will suggest how to implement the right-hand
  64. rule.  First, you will always need to keep track of what direction you're
  65. walking.  Now to simulate the right hand on the wall: check the grid
  66. location in the direction just clockwise to the direction you're walking.
  67. In other words, if you're walking to the right, check the downward
  68. direction.  Is there a wall there?  If not, go in that direction.  But if
  69. there is a wall there, keep checking directions going counter-clockwise
  70. until you find a spot that isn't a wall.  (Using the same example, if you
  71. couldn't go down, check right, then up, then left until you find a
  72. non-wall.)  As soon as you find a non-wall, go in that direction.
  73. ------------------------------------------------------------------------
  74.  
  75. There are probably all sorts of ways to solve a maze, but here is the
  76. approach I use.  First of all, you will need to associate another
  77. boolean variable with each maze location, indicating whether or not
  78. you've passed that spot already while trying to solve the maze.  (Think
  79. of leaving a trail of bread crumbs and you have the right idea.)  Set
  80. all your "bread crumbs" to false.  Now start at the beginning of the
  81. maze, and walk the maze via the right-hand rule.  Whenever you move to
  82. a new location, check to see if there's a bread crumb there already.  If
  83. there is not, put one there, *and also in the location you were just at*.
  84. If there is already a bread crumb there, remove it, *and also remove the
  85. bread crumb from the location you were just at*.  When you finally reach
  86. the exit, the only bread crumbs remaining, will comprise the solution.
  87. (All that bit about "the location you were just at", keeps bread crumbs
  88. from appearing improperly at corners and dead ends.)
  89. }